package com.peng.leetcode.other;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * MedianSlidingWindow
 * <p>
 * 480. 滑动窗口中位数
 *
 * @author: lupeng6
 * @create: 2021/2/3 15:19
 */
public class MedianSlidingWindow {

    public static void main(String[] args) {
//        [1,3,-1,-3,5,3,6,7]
//        3
//        [1,2,3,4,2,3,1,4,2]
//        3
//        [2147483647,2147483647]
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        double[] doubles = new MedianSlidingWindow().medianSlidingWindow(nums, 3);
        Arrays.stream(doubles).forEach(System.out::println);
    }

    PriorityQueue<Integer> left;
    PriorityQueue<Integer> right;


    /**
     * 找到动态数据中的中位数
     *
     * @author lupeng6
     * @date 2021/2/3 15:20
     */
    public double[] medianSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return new double[]{0};
        }

        this.left = new PriorityQueue<>(k, (a, b) -> Integer.compare(b, a));
        this.right = new PriorityQueue<>(k, (a, b) -> Integer.compare(a, b));

        int len = nums.length;
        for (int i = 0; i < k; i++) {
            int num = nums[i];
            right.offer(num);
        }
        for (int i = 0; i < k / 2; i++) {
            left.offer(right.poll());
        }

        int index = 0;
        double[] ans = new double[len - k + 1];

        ans[index++] = getMiddle();

        for (int i = k; i < len; i++) {
            int add = nums[i];
            int delete = nums[i - k];
            if (right.peek() <= add) {
                right.offer(add);
            } else {
                left.offer(add);
            }
            if (right.peek() <= delete) {
                right.remove(delete);
            } else {
                left.remove(delete);
            }

            adjust();
            ans[index++] = getMiddle();
        }

        return ans;
    }

    private void adjust() {
        if ((right.size() - 1) > left.size()) {
            left.offer(right.poll());
        }
        if (left.size() > right.size()) {
            right.offer(left.poll());
        }
    }

    private double getMiddle() {
        int total = left.size() + right.size();
        if (total % 2 == 0) {
            return (left.peek() / 2.0) + (right.peek() / 2.0);
        } else {
            return right.peek() / 1.0;
        }
    }


}
